package com.example.demo.leetcode.top;

import java.util.*;

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 *
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1：
 *
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 *   [7],
 *   [2,2,3]
 * ]
 * 示例 2：
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BTree_组合总和 {

    /**
     * 利用树的思想，进行深度递归处理(累减)
     *  (1)结果==0,是想要的值,结果<0,return
     *  (2)深度遍历的时候需要遍历所有值
     *  (3)如何避免重复的结果集? 深度遍历的时候，之前减掉的值不再使用
     *
     *
     *  如何优化??
     *   (1)先从小到大排序candidates
     *   (2)遍历的时候如果 target<0 可以直接结束循环
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        int length = candidates.length;
        LinkedList<Integer> list = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(candidates,0,length,target,list,res);
        return res;
    }

    /**
     *
     * @param candidates
     * @param begin  每次遍历的起点
     * @param length 遍历的终点
     * @param target 目标值
     * @param list  临时存放数组
     * @param res   最终结果集
     */
    public void dfs(int [] candidates,int begin,int length,int target,List<Integer> list,List<List<Integer>> res){

        if(target < 0 ){
            return;
        }
        if(target == 0){
            res.add(new LinkedList<>(list));
        }

        //从beging开始，每次往下一个节点，begin前移一位，排除过使用过的值
        for(int i=begin;i<length;i++){

            list.add(candidates[i]);

            //下次遍历,起点为i,target减小
            dfs(candidates,i,length,target-candidates[i],list,res);

            list.remove(list.size()-1);
        }

    }

}
